//给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。 
//
// 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 
//
// 示例 1: 
//
// 
//输入: prices = [7,1,5,3,6,4]
//输出: 7
//解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
//     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
// 
//
// 示例 2: 
//
// 
//输入: prices = [1,2,3,4,5]
//输出: 4
//解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
//     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
// 
//
// 示例 3: 
//
// 
//输入: prices = [7,6,4,3,1]
//输出: 0
//解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 
//
// 
//
// 提示： 
//
// 
// 1 <= prices.length <= 3 * 104 
// 0 <= prices[i] <= 104 
// 
// Related Topics 贪心 数组 动态规划 
// 👍 1460 👎 0

package com.cute.leetcode.editor.cn;
public class BestTimeToBuyAndSellStockIi {
    public static void main(String[] args) {
        int[] nums = {7,1,5,3,6,4};
        new BestTimeToBuyAndSellStockIi().new Solution().maxProfit(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 允许多次买卖，但是不能同时持有多支股票，即买入时手中不能有股票
         * 1.使用动态规划：和上一道题目非常像，只不过是可以多次买卖了
         *  这一道题目和上一道题目在动态规划的时候i都是记录的值是[0,i]中所有情况的累加
         *
         *
         */
        public int maxProfit1(int[] prices) {
            int len = prices.length;
            // 特殊判断
            if (len < 2) {
                return 0;
            }
            int[][] dp = new int[len][2];

            // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
            // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数

            // 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价
            dp[0][0] = 0;
            dp[0][1] = -prices[0];

            // 从第 2 天开始遍历
            for (int i = 1; i < len; i++) {
                //今天不持股的时候现金为：max(昨天不持股,昨天持股今天卖了)
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]+prices[i]);
                //TODO 能否多次交易就差在这里
                // 今天持股的时候最大现金为：max(昨天持股今天仍然持股，昨天不持股今天买入了)
                // 如果不允许多次交易的话，昨天不持股的钱是不能算的
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0]-prices[i]);
            }
            return dp[len - 1][0];
        }

        /**
         * 2.贪心算法：只要今天比昨天的价格高我就卖，贪他妈的就完了
         * 这样虽然实际上不讲道理，但是确实符合题目要求
         * 比如为1 2 3 4 5 相加结果为 2-1 + 3-2 + 4-3 + 5-4 = 5-1，还是第一天买入最后一天卖出的结果
         */
        public int maxProfit(int[] prices){
            if (prices.length <2) return 0;
            int res = 0;
            for (int i = 1; i <prices.length ; i++) {
                int diff = prices[i] - prices[i-1];
                if (diff>0) res+=diff;
            }
            return res;
        }

        /**
         * 另一个题解：根据前一天的现金和股票，滚动求解今天的结果
         */
        public int maxProfit3(int[] prices){
            if (prices.length <2) return 0;
            int cash = 0;//手中现金
            int stack = -prices[0];//股票支出
            for (int i = 1; i <prices.length ; i++) {
                //到今天的现金 = Max(昨天的现金，昨天买入今天卖出股票赚的钱)
                cash = Math.max(cash, stack + prices[i]);
               //今天继续买入，可以理解为买卖股票剩下的钱？
                stack = cash - prices[i];
            }
            return cash;
        }

        //二刷的时候动态规划状态想错了，应该定义为是否持股，而不是定义为是否交易
        //最后是用的贪心算法解的这一道题，有利润就交易。

    }
//leetcode submit region end(Prohibit modification and deletion)



















}